package com.base.huawei;

import java.util.Scanner;

public class shopping {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            int[][][] dp = new int[a + 1][b + 1][2];
            // dp[i]表示预算i元，能够获得的最大价值
            int[][] arr = new int[b][3];
            for (int i = 0; i < b; i++) {
                int v = in.nextInt();
                int w = in.nextInt();
                int q = in.nextInt();
                arr[i] = new int[]{v, w, q};
            }
            //初始化
            for (int i = 1; i <= b; i++) {
                //10元 购买一个商品，价值为10元，数量为1
                int v = arr[i - 1][0];
                int w = arr[i - 1][1];
                int q = arr[i - 1][2];
                if (q > 0) {
                    //加入当前元素的价值
                    if (v + arr[q - 1][0] + dp[10][i - 1][1] <= 10) {
                        dp[10][i][0] = dp[10][i-1][0] + v * w + arr[q - 1][0] * arr[q - 1][1];
                        dp[10][i][1] = dp[10][i-1][1] +v+arr[q - 1][0];
                    }
                } else {
                    if (v <= 10) {
                        dp[10][i][0] =dp[10][i-1][0] + v * w;
                        dp[10][i][1] =dp[10][i-1][1] +v;
                    }
                }
            }
            //一件商品
            for (int i = 10; i <= a; i+=10) {
                dp[i][1][0]= dp[10][1][0];
                dp[i][1][1]= dp[10][1][1];
            }


            for (int i = 10; i <= a; i += 10) {
                //预算i元
                for (int j = 1; j <= b; j++) {
                    int v = arr[j][0];
                    int w = arr[j][1];
                    int q = arr[j][2];
                    //预算i比v大
                    if (i >= v) {
                        //加入进来,表示预算i元，能够获得的最大价值
                        if (q > 0) {
                            //加入当前元素的价值
                            if (v + arr[q - 1][0] <= i) {
                                dp[i] = Math.max(dp[i], Math.max(dp[i - v], dp[i - v] + v * w + arr[q - 1][0] * arr[q - 1][1]));
                            }
                        } else {
                            dp[i] = Math.max(dp[i], Math.max(dp[i - v], dp[i - v] + v * w));
                        }
                    }
                }
            }
            System.out.println(dp[a]);
        }
    }
}
// 600 = 1200 是对的
//输入：
//50 5
//20 3 5
//20 3 5
//10 3 0
//10 2 0
//10 1 0

//1000 5
//800 2 0
//400 5 1
//300 5 1
//400 3 0
//500 2 0
